{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 欧拉函数\n",
    "参考: https://zhuanlan.zhihu.com/p/48249182"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "1\n",
      "4\n",
      "6\n",
      "24\n",
      "756\n"
     ]
    }
   ],
   "source": [
    "def euler_function(n):\n",
    "    j = 0\n",
    "    \"\"\"欧几里得算法求是否与n互素\"\"\"\n",
    "    for i in range(2, n):\n",
    "        a = n\n",
    "        q = i\n",
    "        r = a % i\n",
    "        while r != 1 and r != 0:\n",
    "            a = int(q)\n",
    "            q = int(r)\n",
    "            r = int(a) % int(q)\n",
    "        \"\"\"如果互素则计数+1\"\"\"\n",
    "        if r == 1:\n",
    "            j += 1\n",
    "        elif r == 0:\n",
    "            pass\n",
    "    return j + 1\n",
    "\n",
    "print(euler_function(8))\n",
    "print(euler_function(1))\n",
    "print(euler_function(5))\n",
    "print(euler_function(7))\n",
    "print(euler_function(56))\n",
    "print(euler_function(1323))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 欧拉定理"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "2401.0\n"
     ]
    },
    {
     "ename": "OverflowError",
     "evalue": "math range error",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mOverflowError\u001b[0m                             Traceback (most recent call last)",
      "\u001b[1;32mc:\\gitee\\python-learn\\math\\number_thero\\euler_function.ipynb Cell 4'\u001b[0m in \u001b[0;36m<cell line: 6>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/gitee/python-learn/math/number_thero/euler_function.ipynb#ch0000002?line=3'>4</a>\u001b[0m \u001b[39mprint\u001b[39m(math\u001b[39m.\u001b[39mpow(\u001b[39m7\u001b[39m, e10)) \n\u001b[0;32m      <a href='vscode-notebook-cell:/c%3A/gitee/python-learn/math/number_thero/euler_function.ipynb#ch0000002?line=4'>5</a>\u001b[0m e4k \u001b[39m=\u001b[39m euler_function(\u001b[39m4000\u001b[39m)\n\u001b[1;32m----> <a href='vscode-notebook-cell:/c%3A/gitee/python-learn/math/number_thero/euler_function.ipynb#ch0000002?line=5'>6</a>\u001b[0m \u001b[39mprint\u001b[39m(math\u001b[39m.\u001b[39;49mpow(\u001b[39m7\u001b[39;49m, e4k))\n",
      "\u001b[1;31mOverflowError\u001b[0m: math range error"
     ]
    }
   ],
   "source": [
    "e10 = euler_function(10)\n",
    "print(e10)\n",
    "import math\n",
    "print(math.pow(7, e10)) \n",
    "e4k = euler_function(4000)\n",
    "print(e4k)\n",
    "# print(math.pow(7, e4k)) "
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "50447ad957ac0115bfb884f04afa4389b85698be0a7535fa52d95dddcd37b183"
  },
  "kernelspec": {
   "display_name": "Python 3.10.4 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.4"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
